package datastructure.hash;

/**
 * MyHashMap() 用空映射初始化对象
 * void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
 * int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
 * void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。
 */
public class MyHashMap {
    private final Node[] nodes;
    public MyHashMap() {
        nodes = new Node[100000];
    }
    public void put(int key, int value) {
        int index = hash(key);
        Node node = nodes[index];
        if (node == null) {
            nodes[index] = new Node(key, value, null);
        } else {
            do {
                if (node.key == key) {
                    node.val = value;
                    break;
                } else {
                    if (node.next == null) {
                        node.next = new Node(key, value, null);
                        break;
                    }
                    node = node.next;
                }
            }while (true);
        }
    }

    public int get(int key) {
        int index = hash(key);
        Node node = nodes[index];
        while (node != null) {
            if (node.key == key) {
                return node.val;
            } else {
                node = node.next;
            }
        }
        return -1;
    }

    public void remove(int key) {
        int index = hash(key);
        Node node = nodes[index];
        if (node == null) {
            return;
        }
        if (node.key == key) {
            nodes[index] = node.next;
        } else {
            while (node.next != null) {
                if (node.next.key == key) {
                    node.next = node.next.next;
                    break;
                } else {
                    node = node.next;
                }
            }
        }
    }

    private int hash(int key){
        return (key+100000) % nodes.length;
    }
    private static class Node{
        int key;
        int val;
        Node next;
        public Node(int key, int val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }
}
